#include<bits/stdc++.h>
using namespace std;
mt19937 Rnd(time(0));
int n = 50000,m = 50000;
int a[50011];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	freopen("escape.in","w",stdout);
	cout << n << " " << m << "\n";
	for(int i = 2;i <= n;i++)
		cout << (Rnd() % (i - 1) + 1) << " ";
	cout << "\n";
	for(int i = 1;i <= n;i++)
		a[i] = i;
	srand(time(0));
	random_shuffle(a + 1,a + n + 1);
	for(int i = 1;i <= n;i++)
		cout << a[i] << " ";
	cout << "\n";
	for(int i = 1;i <= m;i++)
	{
		int l = Rnd() % n + 1,r = Rnd() % n + 1;
		if(l > r)
			swap(l,r);
		cout << l << " " << r << "\n";
	}
	return 0;
}
